package cn.fansunion.leecode.recursion;

import java.util.HashMap;
import java.util.Map;

/**
 * 爬楼梯
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。
 * @author wen.lei@brgroup.com
 *
 * 2022-1-4
 */
public class ClimbingStairs {
    
    /**
     * 方法1：最简单的递归(leecode上超时了)
     * f(x)=f(x-1)+f(x-2)
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if(n<=0) {
            return 0;
        }
        else if(n==1) {
            return 1;
        }else if(n==2) {
            return 2;
        }else {
            return climbStairs(n-1)+climbStairs(n-2);
        }
    }
    
    //看网友答案，递归时可以加点缓存。还以为可行，其实不行
    //因为是从后向前倒退的，因为前面几个没有计算，继续倒退
    //从小到大累加，才是更快的办法
    Map<Integer,Integer> cache=new HashMap<Integer,Integer>();
    public int climbStairsCache(int n) {
        if(n<=0) {
            return 0;
        }
        else if(n==1) {
            return 1;
        }else if(n==2) {
            return 2;
        }else {
            if(cache.get(n)!=null) {
                return cache.get(n);
            }
            int nValue= climbStairs(n-1)+climbStairs(n-2);
            cache.put(n, nValue);
            return nValue;
        }
    }
    
    /**
     * 方法2：从小到大累加，充分利用每次的计算（滚动数组）
     * f(x)=f(x-1)+f(x-2)，f(1)=1,f(2)=2;f(0)=0不太正常
     * @param n
     * @return
     */
    public int climbStairsDp(int n) {
        if(n<=0) {
            return 0;
        }
        else if(n==1) {
            return 1;
        }else if(n==2) {
            return 2;
        }
        //0不用，感觉没有意义
        int[] array = new int[n+1];
        array[1]=1;
        array[2]=2;
        for(int index=3;index<=n;index++) {
            array[index]=array[index-1]+array[index-2];
        }
        return array[n];
    }
    
    /**
     * 方法3：从小到大累加，充分利用每次的计算(不用数组，空间优化)
     * f(x)=f(x-1)+f(x-2)，f(1)=1,f(2)=2;f(0)=0不太正常
     * @param n
     * @return
     */
    public int climbStairsDpTmpVariable(int n) {
        if(n<=0) {
            return 0;
        }
        else if(n==1) {
            return 1;
        }else if(n==2) {
            return 2;
        }
        //0不用，感觉没有意义
        int dp1=1;
        int dp2=2;
        int dpIndex=0;
        for(int index=3;index<=n;index++) {
            //f(x)=f(x-1)+f(x-2)
            dpIndex=dp1+dp2;
            //向前滚动，复用变量
            dp1=dp2;
            dp2=dpIndex;
        }
        return dpIndex;
    }
    
    //方法4 矩阵快速幂，方法5 通项公式(纯数学了，艹)
}
